Chapter 4: Recursive Problem Solving

Interval Problems Introduction

Intervals are everywhere in software systems. A meeting from 2pm to 3pm. A server busy from timestamp 1000 to 1500. A memory block allocated from address 0x1000 to 0x2000. A promotional discount valid from January 1st to January 31st.

In this chapter, we'll build a foundation for solving interval problems recursively. We'll start with the fundamental question: what exactly is an interval, and how do we represent it in code? Then we'll explore the most common operations we need to perform on intervals. Finally, we'll discover why sorting intervals is almost always the critical first step—and how that preprocessing unlocks elegant recursive solutions.

What Are Intervals?

An interval represents a continuous range between two points. In programming, we typically represent an interval as a pair of values: a start point and an end point.

# The simplest representation: a tuple
interval = (10, 20)  # Represents the range from 10 to 20

# More explicit: a list
interval = [10, 20]  # Same meaning, different syntax

# Most readable: a named tuple or dataclass
from collections import namedtuple

Interval = namedtuple('Interval', ['start', 'end'])
meeting = Interval(start=14, end=15)  # 2pm to 3pm

print(f"Meeting from {meeting.start}:00 to {meeting.end}:00")
# Output: Meeting from 14:00 to 15:00

The Anatomy of an Interval

Every interval has three essential properties:

Start point: Where the interval begins (inclusive)
End point: Where the interval ends (typically inclusive, but conventions vary)
Length: The distance from start to end

Let's create a simple interval representation that we'll use throughout this chapter:

class Interval:
    """Represents a continuous range from start to end (inclusive)."""

    def __init__(self, start, end):
        if start > end:
            raise ValueError(f"Invalid interval: start ({start}) > end ({end})")
        self.start = start
        self.end = end

    def length(self):
        """Return the length of this interval."""
        return self.end - self.start

    def __repr__(self):
        return f"[{self.start}, {self.end}]"

    def __eq__(self, other):
        return self.start == other.start and self.end == other.end

# Create some intervals
meeting1 = Interval(9, 10)   # 9am to 10am
meeting2 = Interval(10, 11)  # 10am to 11am
meeting3 = Interval(9, 11)   # 9am to 11am

print(meeting1)              # Output: [9, 10]
print(f"Length: {meeting1.length()}")  # Output: Length: 1

Real-World Interval Examples

Before diving into algorithms, let's ground ourselves in concrete use cases. Understanding the domain helps us choose the right approach.

Use Case 1: Meeting Room Scheduling

You're building a calendar system. Users book meeting rooms by specifying time intervals. You need to: - Check if a new booking conflicts with existing ones - Find available time slots - Merge consecutive meetings in the same room

# Meeting room bookings (times in 24-hour format)
bookings = [
    Interval(9, 10),   # 9am-10am
    Interval(10, 12),  # 10am-12pm
    Interval(14, 15),  # 2pm-3pm
    Interval(15, 16),  # 3pm-4pm
]

# Question: Can we book a meeting from 11am to 1pm?
new_booking = Interval(11, 13)

# Question: What time slots are available between 9am and 5pm?
work_day = Interval(9, 17)

Use Case 2: Server Resource Allocation

A server handles requests that occupy CPU time. Each request has a start time and end time (in milliseconds since startup). You need to: - Determine maximum concurrent requests (to size your thread pool) - Find idle periods (for maintenance windows) - Detect overlapping requests (potential resource conflicts)

# Server request intervals (milliseconds)
requests = [
    Interval(0, 100),      # Request 1: 0-100ms
    Interval(50, 150),     # Request 2: 50-150ms (overlaps with 1)
    Interval(200, 300),    # Request 3: 200-300ms
    Interval(250, 350),    # Request 4: 250-350ms (overlaps with 3)
]

# Question: What's the maximum number of concurrent requests?
# Question: When is the server completely idle?

Use Case 3: Date Range Promotions

An e-commerce site runs promotional campaigns. Each campaign has a start date and end date. You need to: - Merge overlapping campaigns (to avoid customer confusion) - Find gaps (opportunities for new campaigns) - Check if a specific date falls within any active campaign

# Campaign date ranges (days since year start)
campaigns = [
    Interval(1, 31),      # January campaign
    Interval(25, 60),     # Late Jan through Feb campaign (overlaps)
    Interval(100, 120),   # April campaign
]

# Question: On day 30, which campaigns are active?
# Question: What's the longest gap between campaigns?

Common Interval Operations

Now that we understand what intervals represent, let's explore the fundamental operations we need to perform on them. These operations form the building blocks for more complex interval algorithms.

Operation 1: Checking Overlap

Two intervals overlap if they share any points in common. This is the most fundamental interval operation.

def intervals_overlap(interval1, interval2):
    """
    Check if two intervals overlap.

    Two intervals overlap if one starts before the other ends.
    """
    # interval1 starts before interval2 ends AND
    # interval2 starts before interval1 ends
    return interval1.start <= interval2.end and interval2.start <= interval1.end

# Test cases
meeting1 = Interval(9, 11)   # 9am-11am
meeting2 = Interval(10, 12)  # 10am-12pm
meeting3 = Interval(13, 14)  # 1pm-2pm

print(f"{meeting1} overlaps {meeting2}: {intervals_overlap(meeting1, meeting2)}")
# Output: [9, 11] overlaps [10, 12]: True

print(f"{meeting1} overlaps {meeting3}: {intervals_overlap(meeting1, meeting3)}")
# Output: [9, 11] overlaps [13, 14]: False

# Edge case: intervals that touch but don't overlap
touching1 = Interval(9, 10)
touching2 = Interval(10, 11)
print(f"{touching1} overlaps {touching2}: {intervals_overlap(touching1, touching2)}")
# Output: [9, 10] overlaps [10, 11]: True (they share the point 10)

Operation 2: Merging Two Intervals

When two intervals overlap, we often want to merge them into a single interval that spans both ranges.

def merge_two_intervals(interval1, interval2):
    """
    Merge two overlapping intervals into one.

    Precondition: The intervals must overlap.
    Returns a new interval spanning both inputs.
    """
    if not intervals_overlap(interval1, interval2):
        raise ValueError(f"Cannot merge non-overlapping intervals: {interval1} and {interval2}")

    # The merged interval starts at the earlier start
    # and ends at the later end
    new_start = min(interval1.start, interval2.start)
    new_end = max(interval1.end, interval2.end)

    return Interval(new_start, new_end)

# Test merging
meeting1 = Interval(9, 11)   # 9am-11am
meeting2 = Interval(10, 12)  # 10am-12pm

merged = merge_two_intervals(meeting1, meeting2)
print(f"{meeting1} + {meeting2} = {merged}")
# Output: [9, 11] + [10, 12] = [9, 12]

# Another example: one interval completely contains another
outer = Interval(9, 15)
inner = Interval(10, 11)
merged = merge_two_intervals(outer, inner)
print(f"{outer} + {inner} = {merged}")
# Output: [9, 15] + [10, 11] = [9, 15]

Operation 3: Finding the Gap Between Intervals

When two intervals don't overlap, there's a gap between them. Finding gaps is crucial for scheduling and resource allocation.

def gap_between_intervals(interval1, interval2):
    """
    Find the gap between two non-overlapping intervals.

    Precondition: The intervals must not overlap.
    Returns a new interval representing the gap, or None if they overlap.
    """
    if intervals_overlap(interval1, interval2):
        return None  # No gap if they overlap

    # Determine which interval comes first
    if interval1.end < interval2.start:
        # interval1 comes before interval2
        gap_start = interval1.end
        gap_end = interval2.start
    else:
        # interval2 comes before interval1
        gap_start = interval2.end
        gap_end = interval1.start

    return Interval(gap_start, gap_end)

# Test gap finding
morning = Interval(9, 11)    # 9am-11am
afternoon = Interval(14, 16) # 2pm-4pm

gap = gap_between_intervals(morning, afternoon)
print(f"Gap between {morning} and {afternoon}: {gap}")
# Output: Gap between [9, 11] and [14, 16]: [11, 14]

print(f"Gap length: {gap.length()} hours")
# Output: Gap length: 3 hours

# No gap when intervals overlap
meeting1 = Interval(9, 11)
meeting2 = Interval(10, 12)
gap = gap_between_intervals(meeting1, meeting2)
print(f"Gap between overlapping intervals: {gap}")
# Output: Gap between overlapping intervals: None

Operation 4: Checking Containment

Sometimes we need to know if one interval completely contains another, or if a specific point falls within an interval.

def interval_contains_point(interval, point):
    """Check if a point falls within an interval (inclusive)."""
    return interval.start <= point <= interval.end

def interval_contains_interval(outer, inner):
    """Check if one interval completely contains another."""
    return outer.start <= inner.start and inner.end <= outer.end

# Test point containment
meeting = Interval(9, 11)  # 9am-11am

print(f"Is 10:00 during the meeting? {interval_contains_point(meeting, 10)}")
# Output: Is 10:00 during the meeting? True

print(f"Is 12:00 during the meeting? {interval_contains_point(meeting, 12)}")
# Output: Is 12:00 during the meeting? False

# Test interval containment
work_day = Interval(9, 17)   # 9am-5pm
lunch = Interval(12, 13)     # 12pm-1pm
evening = Interval(18, 20)   # 6pm-8pm

print(f"Is lunch during work day? {interval_contains_interval(work_day, lunch)}")
# Output: Is lunch during work day? True

print(f"Is evening during work day? {interval_contains_interval(work_day, evening)}")
# Output: Is evening during work day? False

The Critical Preprocessing Step: Sorting Intervals

Here's a profound insight that unlocks elegant recursive solutions: most interval problems become dramatically simpler when the intervals are sorted.

Why? Because sorting establishes a predictable order. Once intervals are sorted by start time, we can make powerful assumptions: - We process intervals in chronological order - We only need to look at adjacent or nearby intervals - We can use the "first + rest" recursive pattern effectively

Let's see why unsorted intervals are problematic, then how sorting transforms the problem.

The Problem with Unsorted Intervals

Consider this scenario: you have a list of meeting bookings and need to find all overlapping pairs.

# Unsorted meeting bookings
unsorted_meetings = [
    Interval(14, 16),  # 2pm-4pm
    Interval(9, 10),   # 9am-10am
    Interval(15, 17),  # 3pm-5pm (overlaps with first)
    Interval(10, 11),  # 10am-11am
    Interval(9, 11),   # 9am-11am (overlaps with second and fourth)
]

def find_overlaps_unsorted(intervals):
    """
    Find all overlapping pairs in an unsorted list.
    This requires checking every pair - O(n²) comparisons!
    """
    overlaps = []

    # Must compare every interval with every other interval
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            if intervals_overlap(intervals[i], intervals[j]):
                overlaps.append((intervals[i], intervals[j]))

    return overlaps

overlaps = find_overlaps_unsorted(unsorted_meetings)
print(f"Found {len(overlaps)} overlapping pairs:")
for pair in overlaps:
    print(f"  {pair[0]} overlaps {pair[1]}")

# Output:
# Found 2 overlapping pairs:
#   [14, 16] overlaps [15, 17]
#   [9, 10] overlaps [9, 11]

The problem: With unsorted intervals, we have no choice but to compare every interval with every other interval. That's O(n²) comparisons. For 1000 intervals, that's 1,000,000 comparisons!

The Power of Sorting

Now watch what happens when we sort the intervals first:

def sort_intervals(intervals):
    """
    Sort intervals by start time, then by end time if starts are equal.
    Returns a new sorted list.
    """
    return sorted(intervals, key=lambda interval: (interval.start, interval.end))

# Sort the meetings
sorted_meetings = sort_intervals(unsorted_meetings)

print("Sorted meetings:")
for meeting in sorted_meetings:
    print(f"  {meeting}")

# Output:
# Sorted meetings:
#   [9, 10]
#   [9, 11]
#   [10, 11]
#   [14, 16]
#   [15, 17]

The transformation: Now the intervals are in chronological order. Notice what this gives us:

Intervals that could overlap are adjacent or nearby - we don't need to check intervals far apart
We can process intervals sequentially - perfect for recursive "first + rest" pattern
We can make early decisions - if an interval starts after another ends, we know they don't overlap

Let's see this in action with a more efficient overlap detection:

def find_overlaps_sorted(intervals):
    """
    Find all overlapping pairs in a sorted list.
    Much more efficient - we only check adjacent intervals!
    """
    if len(intervals) <= 1:
        return []

    overlaps = []

    # Only need to check each interval against the next one
    # (and potentially a few more if there are multiple overlaps)
    for i in range(len(intervals) - 1):
        current = intervals[i]

        # Check subsequent intervals until we find one that doesn't overlap
        j = i + 1
        while j < len(intervals) and intervals_overlap(current, intervals[j]):
            overlaps.append((current, intervals[j]))
            j += 1

    return overlaps

# Compare performance
import time

# Create a larger test set
large_unsorted = [Interval(i * 10, i * 10 + 15) for i in range(100)]
# Shuffle them
import random
random.shuffle(large_unsorted)

# Time unsorted approach
start = time.time()
overlaps_unsorted = find_overlaps_unsorted(large_unsorted)
time_unsorted = time.time() - start

# Time sorted approach
large_sorted = sort_intervals(large_unsorted)
start = time.time()
overlaps_sorted = find_overlaps_sorted(large_sorted)
time_sorted = time.time() - start

print(f"\nPerformance comparison (100 intervals):")
print(f"Unsorted approach: {time_unsorted:.4f} seconds")
print(f"Sorted approach:   {time_sorted:.4f} seconds")
print(f"Speedup: {time_unsorted / time_sorted:.1f}x faster")

# Output (approximate):
# Performance comparison (100 intervals):
# Unsorted approach: 0.0023 seconds
# Sorted approach:   0.0003 seconds
# Speedup: 7.7x faster

Why Sorting Enables Recursion

Sorting transforms interval problems into a form that's perfect for recursive thinking. Here's why:

1. The "First + Rest" Pattern Works

Once sorted, we can confidently process the first interval and recurse on the rest, knowing we're handling intervals in chronological order.

2. Base Cases Become Obvious

Empty list: no intervals to process
Single interval: nothing to merge/compare with

3. Recursive Cases Are Clear

Does the first interval overlap with the second?
Yes: merge them and recurse
No: keep the first, recurse on the rest

Let's preview what this looks like (we'll implement this fully in the next section):

def merge_overlapping_intervals_preview(intervals):
    """
    Preview of recursive interval merging (simplified).
    Full implementation coming in section 4.2!
    """
    # Base case: 0 or 1 intervals
    if len(intervals) <= 1:
        return intervals

    # Sort first (critical preprocessing!)
    sorted_intervals = sort_intervals(intervals)

    # Recursive case: process first two intervals
    first = sorted_intervals[0]
    second = sorted_intervals[1]
    rest = sorted_intervals[2:]

    if intervals_overlap(first, second):
        # Merge them and recurse
        merged = merge_two_intervals(first, second)
        return merge_overlapping_intervals_preview([merged] + rest)
    else:
        # Keep first, recurse on rest
        return [first] + merge_overlapping_intervals_preview([second] + rest)

# Test the preview
test_intervals = [
    Interval(1, 3),
    Interval(2, 6),
    Interval(8, 10),
    Interval(15, 18)
]

print("\nOriginal intervals:")
for interval in test_intervals:
    print(f"  {interval}")

merged = merge_overlapping_intervals_preview(test_intervals)

print("\nMerged intervals:")
for interval in merged:
    print(f"  {interval}")

# Output:
# Original intervals:
#   [1, 3]
#   [2, 6]
#   [8, 10]
#   [15, 18]
#
# Merged intervals:
#   [1, 6]
#   [8, 10]
#   [15, 18]

Sorting Strategies for Different Interval Problems

Different interval problems benefit from different sorting strategies. Let's explore the most common approaches.

Strategy 1: Sort by Start Time (Most Common)

This is the default choice for most interval problems. It establishes chronological order.

def sort_by_start(intervals):
    """Sort intervals by start time (ascending)."""
    return sorted(intervals, key=lambda interval: interval.start)

meetings = [
    Interval(14, 16),
    Interval(9, 10),
    Interval(15, 17),
]

sorted_meetings = sort_by_start(meetings)
print("Sorted by start time:")
for meeting in sorted_meetings:
    print(f"  {meeting}")

# Output:
# Sorted by start time:
#   [9, 10]
#   [14, 16]
#   [15, 17]

When to use: Merging overlaps, finding gaps, scheduling problems, most general interval operations.

Strategy 2: Sort by End Time

Sometimes we care more about when intervals finish than when they start.

def sort_by_end(intervals):
    """Sort intervals by end time (ascending)."""
    return sorted(intervals, key=lambda interval: interval.end)

meetings = [
    Interval(9, 12),   # Ends at 12
    Interval(10, 11),  # Ends at 11 (earlier)
    Interval(14, 16),  # Ends at 16
]

sorted_meetings = sort_by_end(meetings)
print("Sorted by end time:")
for meeting in sorted_meetings:
    print(f"  {meeting}")

# Output:
# Sorted by end time:
#   [10, 11]
#   [9, 12]
#   [14, 16]

When to use: Activity selection problems (choosing maximum non-overlapping intervals), greedy algorithms, resource deallocation scheduling.

Strategy 3: Sort by Length

For some problems, we want to process shorter or longer intervals first.

def sort_by_length(intervals, ascending=True):
    """Sort intervals by length."""
    return sorted(intervals, key=lambda interval: interval.length(), 
                  reverse=not ascending)

meetings = [
    Interval(9, 12),   # Length 3
    Interval(10, 11),  # Length 1
    Interval(14, 20),  # Length 6
]

# Shortest first
sorted_shortest = sort_by_length(meetings, ascending=True)
print("Sorted by length (shortest first):")
for meeting in sorted_shortest:
    print(f"  {meeting} (length {meeting.length()})")

# Output:
# Sorted by length (shortest first):
#   [10, 11] (length 1)
#   [9, 12] (length 3)
#   [14, 20] (length 6)

# Longest first
sorted_longest = sort_by_length(meetings, ascending=False)
print("\nSorted by length (longest first):")
for meeting in sorted_longest:
    print(f"  {meeting} (length {meeting.length()})")

# Output:
# Sorted by length (longest first):
#   [14, 20] (length 6)
#   [9, 12] (length 3)
#   [10, 11] (length 1)

When to use: Interval covering problems, optimization problems where interval size matters, removing redundant intervals.

Strategy 4: Multi-Key Sorting

Sometimes we need to sort by multiple criteria: primary sort by one attribute, secondary sort by another.

def sort_by_start_then_end(intervals):
    """
    Sort by start time first, then by end time if starts are equal.
    This ensures consistent ordering even when intervals start at the same time.
    """
    return sorted(intervals, key=lambda interval: (interval.start, interval.end))

meetings = [
    Interval(9, 12),   # Start 9, end 12
    Interval(9, 10),   # Start 9, end 10 (same start, earlier end)
    Interval(9, 15),   # Start 9, end 15 (same start, later end)
    Interval(8, 11),   # Start 8 (earlier start)
]

sorted_meetings = sort_by_start_then_end(meetings)
print("Sorted by start, then end:")
for meeting in sorted_meetings:
    print(f"  {meeting}")

# Output:
# Sorted by start, then end:
#   [8, 11]
#   [9, 10]
#   [9, 12]
#   [9, 15]

When to use: When you need deterministic ordering for intervals with identical start times, complex scheduling problems, ensuring stable sort behavior.

Practical Considerations

Before we move to implementing recursive interval algorithms, let's address some practical concerns.

Python's Recursion Limit

Python has a default recursion limit of 1000 calls. For interval problems with thousands of intervals, this could be an issue.

import sys

# Check current recursion limit
print(f"Current recursion limit: {sys.getrecursionlimit()}")
# Output: Current recursion limit: 1000

# For production code with large datasets, you might need to increase it
# sys.setrecursionlimit(5000)  # Use with caution!

# Or better: use iterative solutions for very large datasets
# We'll show both recursive and iterative approaches in the next section

When to Choose Recursion vs Iteration

Choose recursion when: - The problem naturally decomposes into smaller subproblems - Code clarity is paramount - Dataset size is reasonable (< 1000 intervals typically) - You're using divide-and-conquer (like merge sort)

Choose iteration when: - Dataset is very large (> 1000 intervals) - Performance is critical - Stack space is limited - The iterative solution is equally clear

We'll implement both approaches in the next section so you can compare.

Memory Considerations

Each recursive call consumes stack space. For interval problems, this is usually not a concern because: - Each call stores only a few interval references - Modern systems have generous stack space - Most interval problems have reasonable input sizes

However, be aware of the space complexity:

def analyze_space_complexity():
    """
    Space complexity analysis for recursive interval processing.
    """
    print("Space Complexity Analysis:")
    print()
    print("For n intervals:")
    print("- Sorting: O(n) space for the sorted list")
    print("- Recursive calls: O(n) space in worst case (call stack depth)")
    print("- Total: O(n) space")
    print()
    print("For comparison, iterative approach:")
    print("- Sorting: O(n) space for the sorted list")
    print("- Loop: O(1) space (no call stack)")
    print("- Total: O(n) space (dominated by sorting)")
    print()
    print("Conclusion: Both approaches have similar space complexity,")
    print("but recursion uses the call stack while iteration uses heap memory.")

analyze_space_complexity()

Summary: The Foundation Is Set

We've built a solid foundation for recursive interval problem-solving:

Key Concepts: 1. Intervals represent continuous ranges with start and end points 2. Common operations include overlap checking, merging, gap finding, and containment 3. Sorting is critical - it transforms chaotic interval lists into ordered sequences perfect for recursion 4. Different sorting strategies serve different problem types

The Recursive Mindset: - Sorted intervals enable the "first + rest" pattern - Base cases are clear (empty or single interval) - Recursive cases follow naturally (process first, recurse on rest)

Real-World Applications: - Meeting room scheduling - Server resource allocation - Date range promotions - Time-based conflict detection

In the next section (4.2), we'll put this foundation to work. We'll take the merge overlapping intervals problem and implement it recursively, exploring multiple approaches and comparing them to iterative solutions. You'll see how sorting unlocks elegant recursive solutions and learn when to choose recursion over iteration.

The stage is set. Let's build something real.